This invention relates to the generation of random digital signals, and particularly to a pseudo-random number generator which may be used for encoding in communication systems.
Pseudo-random sequences are useful in a wide variety of applications such as security encoding and decoding, error correction, encoding, radar, and system testing and have been used in electronic bingo number generators. Pseudo-random number generators are well-known in data enciphering means in which a transmitted data pulse stream is modified in accordance with a random sequence of digits. The modified pulse stream may only be deciphered by a decoder embodying knowledge of that random number sequence. In order to provide for increased security, it is desirable that the random number sequence be made long so as to impede the capability of deciphering by an undesired party.
A common component of typical pseudo-random number generators is a shift register. In typical digital enciphering schemes, a shift register is used having taps at least first and second stages thereof, the first and second stages not necessarily being adjacent. The taps are connected to modulo two adders and/or AND gates providing outputs for many different known forms of processing. During successive time periods, which may be called bit times, clock times, or cycles, digits are shifted from each stage to the next. Thus digits from prior stages are shifted into the stages with taps to provide outputs to provide numbers to be operated upon.
The number of different logical functions which may be obtained by use of modulo two addition or ANDing is related to the number of taps on a shift register. Generally, the number of instructions which can be performed by such an enciphering circuit within one bit time is related to the number of taps utilized in the shift register. For most prior embodiments, in order to provide complex interaction between stages, many inter-pin connections on a shift register must be made. Further, if it is desired to alter the functions performed by a shift register, a large number of tap lines must be physically rewired or otherwise logically gated in order to modify the sequence.
The number of pins on a shift register increases linearly with the length thereof, i.e., with the number of stages in the shift register. The physical length of a shift register is limited as a practical matter. Parallel output shift registers are not feasible beyond a few tens of bits per package since the cost thereof and difficulty of connections becomes prohibitive. The limitation on the length of the shift register limits the length of the pseudo-random sequence which can be generated in a one shift register circuit. Longer more complex sequences can be generated only with additional complexity and expense in logic circuitry.